
#include <iostream>
#include <cstring>
#include <time.h>

typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
ll heapcompert = 0;
ll heapswap = 0;
ll quickcompert = 0;
ll quickswap = 0;
ll merge_swap_cnt = 0,merge_com_cnt = 0;
int arr[N];
//merge
int tem[N];
int n;
void print() {
	for (int i = 1; i <= n; i++)cout << arr[i] << " ";
	cout << "\n";
}
void reset(int n) {
	for (int i = 1; i <= n; i++) {
		//产生随机数
		arr[i] = rand() % 100 + 1;
	}
}
void insert_sort() {
	int compertimes = 0;
	int swaptimes = 0;
	for (int i = 2; i <= n; i++) {
		int key = arr[i];
		int j = i - 1;
		while (j >= 0) {
			compertimes++;
			if (arr[j] > key) {
				swaptimes++;
				arr[j + 1] = arr[j];
				j--;
			} else {
				break;
			}
			
		}
		arr[j + 1] = key;
	}
	cout << "直接插入排序 比较次数:" << compertimes << "  移动次数: " << swaptimes << endl;
}
void insert_sort_Shell() {
	int compertimes = 0;
	int swaptimes = 0;
	for (int d = n / 2; d >= 1; d = d / 2) {
		for (int i = d + 1; i <= n; i++) { //将r[i]插入到所属的子序列中
			arr[0] = arr[i];                   //暂存待插入记录
			int j = i - d;               //j指向所属子序列的最后一个记录
			while (j >= 0) {
				compertimes++;
				if (arr[0] < arr[j]) {
					swaptimes++;
					arr[j + d] = arr[j];   //记录后移d个位置
					j = j - d;        //比较同一子序列的前一个记录
				} else {
					break;
				}
				
			}
			arr[j + d] = arr[0];
		}
	}
	//print();
	cout << "希尔排序 比较次数:" << compertimes << "  移动次数: " << swaptimes << endl;
}



void select_sort() {
	int compertimes = 0;
	int swaptimes = 0;
	for (int i = 1; i <= n; i++) {
		int min = i;
		for (int j = i + 1; j <= n; j++) {
			compertimes++;
			if (arr[j] < arr[min]) {
				
				min = j;
			}
		}
		if (min != i) {
			swap(arr[i], arr[min]);
			swaptimes++;
		}
		
	}
	//print();
	cout << "选择排序 比较次数:" << compertimes << "  交换次数: " << swaptimes << endl;
}
//堆调整函数
void shift(int k, int m ) {
	//要筛选结点的编号为k，堆中最后一个结点的编号为m
	int i = k;
	int j = 2 * i;
	while (j <= m ) {       //筛选还没有进行到叶子
		heapcompert++;
		if (j < m && arr[j] < arr[j + 1]) {
			j++;  //左右孩子中取较大者
			
		}
		if (arr[i] > arr[j]) {
			break;    //根比孩子大，符合堆定义
		} else {
			swap(arr[i], arr[j]);
			i = j;
			j = 2 * i; //将最大者与根交换
			heapswap++;                                         //对子树继续调整
		}
	}
}

void select_sort_Heap() {
	for (int i = n / 2; i >= 1; i--) //初建堆
		shift(i, n) ;
	for (int i = 1; i < n; i++ ) {
		swap(arr[1], arr[n - i + 1]); //移走堆顶
		heapswap++;
		shift(1, n - i);             //重建堆
	}
	cout << "堆排序 比较次数:" << heapcompert << "  交换次数: " << heapswap << endl;
}

void swap_sort_bubble() {
	int compertimes = 0;
	int swaptimes = 0;
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= n - i; j++) {
			compertimes++;
			if (arr[j] > arr[j + 1]) {
				swaptimes++;
				swap(arr[j], arr[j + 1]);
			}
		}
	}
	
	cout << "冒泡排序 比较次数:" << compertimes << "  交换次数: " << swaptimes << endl;
}
void quick(int l, int r) {
	if (l >= r) return;
	int i = l - 1, j = r + 1, x = arr[(l + r) / 2];
	while (i < j) {
		do {
			quickcompert++;
			i++;
		} while (arr[i] < x);
		do {
			quickcompert++;
			j--;
		} while (arr[j] > x);
		if (i < j) {
			quickswap++;
			swap(arr[i], arr[j]);
		}
		
	}
	quick(l, j), quick(j + 1, r);
}
void swap_sort_quick(int l, int r) {
	quick(l, r);
	cout << "快速排序 比较次数:" << quickcompert << " 交换次数为： " << quickswap << endl;
}
void merge_sort(int l,int r)
{
	
	if (l >= r) return;
	
	int mid = l + r >> 1;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
	{
		if (arr[i] <= arr[j])
		{
			tem[k ++ ] = arr[i ++ ];
		}	
		else 
		{
			tem[k ++ ] = arr[j ++ ];
		}
		merge_com_cnt++;
	}
		
	while (i <= mid) tem[k ++ ] = arr[i ++ ],merge_swap_cnt++;
	while (j <= r) tem[k ++ ] = arr[j ++ ],merge_swap_cnt++;
	
	for (i = l, j = 0; i <= r; i ++, j ++ ) arr[i] = tem[j],merge_swap_cnt++;
	
}
void merge()
{
	merge_sort(1,n);
	cout << "宾归并排序 比较次数:" << merge_com_cnt << " 交换次数为： " << merge_swap_cnt << endl;
}
int main() {
	cin >> n;
	
	reset(n);
	//快排
	clock_t start, end;
	start = clock();
	swap_sort_quick(1, n);
	end = clock();
	cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
	reset(n);
	//插入排序
	start = clock();
	insert_sort();
	end = clock();
	cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
	reset(n);
	//希尔排序
	start = clock();
	insert_sort_Shell();
	end = clock();
	cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
	reset(n);
	//选择排序
	start = clock();
	select_sort();
	end = clock();
	cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
	reset(n);
	//堆排序
	start = clock();
	select_sort_Heap();
	end = clock();
	cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
	reset(n);
	//冒泡排序
	start = clock();
	swap_sort_bubble();
	end = clock();
	cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
	reset(n);
	//归并排序
	start = clock();
	merge();
	end = clock();
	cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
	return 0;
}
/*
对各个排序算法的性能比较
swap_sort_bubble() -> O(n^2) insert_sort() -> O(n^2) select_sort() -> O(n^2)
swap_sort_quick() -> O(nlogn)
 */